package cn.edu.njust.alg;

//堆排序
public class HeapSortImpl {

	public static void mkheap(int[] a) {
		for (int i = a.length / 2; i >= 0; i--) {
			maxheap(a, a.length, i);
		}
	}

	/**
	 * @param a
	 * @param heapsize
	 * @param index
	 */
	public static void maxheap(int[] a, int heapsize, int index) {
		int left = 2 * index + 1;
		int right = 2 * index + 2;
		int largest = index;
		if (left < heapsize && a[left] > a[largest]) {
			largest = left;
		}
		if (right < heapsize && a[right] > a[largest]) {
			largest = right;
		}

		if (largest == index) {
			return;
		} else {
			ArrayUtils.swap(a, largest, index);
			maxheap(a, heapsize, largest);
		}
	}

	public static void heapsort(int[] a) {
		mkheap(a);
		for (int i = a.length - 1; i > 0; i--) {
			ArrayUtils.swap(a, 0, i);
			maxheap(a, i, 0);
		}
	}

	public static void main(String[] args) {

		int[] a = { 234, 3, 43, 68, 392, 342, 956, 32 };
		ArrayUtils.printArray(a);
		heapsort(a);
		ArrayUtils.printArray(a);

	}
}
